Public Class ArbolAVL<E>
    Public raiz As Nodo<E>

    Public Sub New()

    End Sub

    Public Sub inserta(ByRef padre As Nodo, ByVal valor As Integer)
        If padre Is Nothing Then
            padre = New Nodo<E>
            padre.value = valor
        Else
            If padre.value > valor Then
                inserta(padre.izqda, valor)
            ElseIf padre.value < valor Then
                inserta(padre.drcha, valor)
            End If
        End If
    End Sub

    Public Sub Equilibrio(ByRef n As Nodo)
        'TODO 'Multihilos
        Select Case Altura(n).X - Altura(n).Y
            Case Is = -2
                If Altura(n.drcha).X > Altura(n.drcha).Y Then
                    RDD(n)
                Else
                    RSD(n)
                End If
            Case Is = 2
                If Altura(n.izqda).X > Altura(n.izqda).Y Then
                    RSI(n)
                Else
                    RDI(n)
                End If
            Case Is = -1, 1
                Equilibrio(n.izqda)
                Equilibrio(n.drcha)
        End Select
    End Sub

    Public Sub RSI(ByRef Pivote As Nodo)
        Dim k3 = Pivote.izqda.izqda, k1 = Pivote, k2 = Pivote.izqda
        k3.drcha = k1.izqda
        k2.izqda = k1.drcha
        k1.drcha = k2
        k1.izqda = k3
        Pivote = k2
    End Sub

    Public Sub RDI(ByRef Pivote As Nodo)
        Dim k1 = Pivote.izqda.drcha, k2 = Pivote, k3 = Pivote.izqda
        k3.drcha = k1.izqda
        k2.izqda = k1.drcha
        k1.drcha = k2
        k1.izqda = k3
        Pivote = k1
    End Sub

    Public Sub RSD(ByRef Pivote As Nodo)
        Dim k3 = Pivote.drcha.drcha, k1 = Pivote, k2 = Pivote.drcha
        k3.drcha = k1.izqda
        k2.izqda = k1.drcha
        k1.drcha = k2
        k1.izqda = k3
        Pivote = k2
    End Sub

    Public Sub RDD(ByRef Pivote As Nodo)
        Dim k1 = Pivote.drcha.izqda, k2 = Pivote, k3 = Pivote.drcha
        k2.drcha = k1.izqda
        k3.izqda = k1.drcha
        k1.izqda = k2
        k1.drcha = k3
        Pivote = k1
    End Sub

    Public Function Altura(ByRef N As Nodo<E>) As Point
        If N Is Nothing OrElse N.izqda Is Nothing And N.drcha Is Nothing Then
            Return New Point(0, 0)
        End If
        Dim a As Point = Altura(N.izqda)
        Dim b As Point = Altura(N.drcha)
        Dim x As Integer = Math.Max(a.X, a.Y) + 1
        Dim y As Integer = Math.Max(b.X, b.Y) + 1
        Return New Point(x, y)
    End Function
End Class

Public Class Nodo<E>
    Public izqda As Nodo<E>, drcha As Nodo<E>
    Public value As E
End Class
